/**
 * FileName: RandomArrayQUEUE.c
 * ---------------------------------------------------------------------------------------
 * Program 18.11 Random queue implementation
 * ---------------------------------------------------------------------------------------
 * When we remove an item from this data structure, it is equally likely to be any one of the items currently
 * in the data structure.
 *
 * We can use this code to implement the generalized-queue ADT for graph searching to search a graph
 * in a “random” fashion (see text).
 *
 */
#include <stdlib.h>
#include "GQ.h"

static Item *s;
static int N;

void GQinit(int maxN) {
    s = malloc(sizeof(Item) * maxN);
    N = 0;
}

int GQempty() {
    return N == 0;
}
void GQput(Item x) {
    s[N++] = x;
}
void GQupdate(Item x) {
    //TODO
}
Item GQget() {
    Item t;

    int i = N * (rand()/(RAND_MAX+1.0));
    t = s[i];
    s[i] = s[N-1];
    s[N-1] = t;
    return s[--N];
}
